COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\centerline{Readings in Formal Theories of Knowledge: Prospectus}
C00026 ENDMK
C⊗;
\centerline{Readings in Formal Theories of Knowledge: Prospectus}

{\obeylines
Leora Morgenstern
IBM T.J. Watson Research Center
P.O. Box 704, Mail Stop H1-N08
Yorktown Heights, N.Y. 10598

Lynn Andrea Stein
Brown University
Department of Computer Science
Providence, R.I. 02912}

Over the past several years, there has been a burgeoning interest among
the AI community in formal logics of knowledge.
This interest is attested to by the growing number of papers in formal
logics of knowledge in major AI conferences (such as IJCAI and
AAAI), and the development and growth of conferences
devoted exclusively to this and related topics
(such as the biannual Conference on Theoretical Aspects
of Reasoning About Knowledge  and the
Conference on Principles of Knowledge Representation and Reasoning).
Researchers in
various areas of AI,  such as learning, planning, natural language processing,
and intelligent data bases  believe that a formal theory of
knowledge is a prerequisite to the development of robust AI systems.
For example, an agent who intends to get information from another agent
must be able to reason about what the second agent knows.
Likewise, an agent who plans to perform tasks
in a reasonably complex environment must be able to reason about the
knowledge required to perform an action, to determine whether or
not he has that knowledge, and to plan to get any information
that may be missing.
An integrated theory of knowledge and action is
thus an important part of any robust planning system.  Similarly, in order
to construct a mechanical agent who can function with limited resources,
and reason under time constraints, one should have a theory of knowledge
that does not assume that agents always reason perfectly.

A large number of significant papers attest to the growing interest
and activity in formal theories of knowledge.  To date, however,
this work has not been collected in any systematic manner, and has not been
addressed in significant detail in a textbook.  Each of the two
proceedings of the Conference on Theoretical Aspects of Reasoning
About Knowledge consists of a collection of papers concerning formal
theories of knowledge.
Thse collections, however, do not always meet the need of AI researchers.
In the first place, these
workshops were multidisciplinary efforts; as a result, their proceedings
contain many papers in areas outside of Artificial Intelligence that are
of only peripheral interest to AI researchers.  Secondly, many of the
papers are too advanced to be readily accessible to those who do not have
extensive formal training in the area.  Thirdly, these proceedings
for the most part do not include the seminal works on formal theories
of knowledge.

Likewise, several recent textbooks, including  Nilsson and Genesereth:
{\it Logical Foundations of Artificial Intelligence}
and Davis:
{\it Representations of Knowledge for Commonsense Reasoning}
have spent some time addressing
the general area of formal theories of knowledge.  Due to time and
space constraints, however, their treatments are too elementary
for the serious researcher.

Our book,
{\it 
Readings in Formal Theories of Knowledge},
is intended to serve both as the standard reference for researchers studying
formal logics of knowledge, as well as the introductory volume for those
who would like to become familiar with the area.
In this latter capacity,
it should prove particularly useful as the readings book for a special
topics graduate course, and would provide useful background material
for a novice attempting more advanced work in the area.
As envisioned,
{\it 
Readings in Formal Theories of Knowledge}
will perform the following functions:

1. 
It will collect the most important papers on the theory of knowledge -
from an AI perspective -
in a single volume.
These include not only papers in Artificial Intelligence, but papers
from the areas of philosophy, logic, and distributed computing as well.
Many of these papers, in particular the
philosophical papers, are quite difficult to get hold of.

2. 
It will provide a significant amount of
introductory and supplemental material providing
the background necessary for understanding the papers in the collection.
Computer scientists, even those with a fair amount of training in logic,
often do not have enough background to comprehend in-depth
advanced articles in specialized areas of logic.

For example, one of the proposed sections of
{\it 
Readings in Formal Theories of Knowledge
}
will consist of papers concerning the Knower Paradox.  It is impossible
to fully understand these papers, however, without an understanding
of the closely related Liar Paradox and the various resolutions that have been proposed
to this paradox.  Introductory material at the beginning of this
section will summarize the major work that has been done on the
Liar Paradox.

3. 
It will present, on a section by section basis,
supplementary critiques and analyses of all the papers in the
collection.   Special emphasis will be placed on comparing the papers
within a particular section.  Since research in
formal logics of knowledge is still in a relatively early stage,
there has been little critical work comparing existing articles.
Such critiques are essential, however,
since one cannot fully appreciate the contribution of a particular
piece of research until it is has been placed in context.
For example, it is difficult to appreciate the contribution of
Ernie Davis's "Inferring Ignorance from the Locality of Visual
Perception" unless one is aware of the sketchy treatment of negative
introspection in previous theories of knowledge and action.

{\it
Readings in Formal Theories of Knowledge}
will contain five sections:

Philosophical Foundations:

The logical and philosophical foundations underlying current theories
of knowledge.  This section will include the early work of modern
philosophers such as Hintikka on epistemic logic, as well as
the groundbreaking work of AI researchers McCarthy and Hayes in this
area.

Paradoxes:

A selection of papers addressing the infamous Knower Paradox,
the paradox which plagues sufficiently expressive theories of
knowledge.  Included will be the initial formal presentation
of this and related paradoxes, and representative papers
giving resolutions to this paradox.

Knowledge and Action:

Presentation of research attempting to combine formal theories
of knowledge with formal theories of action.  Particular
questions addressed include: how much knowledge does an
agent need to perform an action? and how do an agent's
actions affect his knowledge?

Consequential Closure:

Presentation of research on a particularly difficult problem
in epistemic logic.  Traditional theories of knowledge assume
that all agents are perfect reasoners, a clearly unrealistic
and overly strong assumption.  These papers discuss ways
to remove such assumptions and what
alternative characterizations
of an agent's reasoning ability might be.

Epistemic Logics and Non-monotonic Logics:

Papers discussing the connection between theories of knowledge and
belief and theories of default reasoning.  This section includes
applications of epistemic logic, such as Shoham's solution
to the Yale Shooting Problem and Halpern and Moses's characterization
of ignorance, and applications of Non-monotonic Logics to epistemic
theories, such as Moore's Autoepistemic Logic.

A proposed list of the papers in
{\it 
Readings in Formal Theories of Knowledge}
is attached to this prospectus.


Now comes the reading list:

Readings in Formal Theories of Knowledge:

Proposed List of Papers

obeylines{
Leora Morgenstern, I.B.M T.J. Watson Research Center
Lynn Andrea Stein, Brown University}

Introduction

[10 -15 pages: Motivation, survey of the various subfields of this area of research]

Philosophical Foundations

Introduction [5-7 pages,
including brief sketch of first order propositional logic and modal
logic]

Plato: Theatetus

Hintikka, J.:  Selection from
Knowledge and Belief: An Introduction to the Logic of the Two Notions,
Cornell University Press, Ithaca, 1962

Hintikka, J.:  "Semantics for Propositional Attitudes"  in
J.Hintikka, ed.:
Models for Modalities,
D. Reidel, 1969

Quine, W.V.O.: "Quantifiers and Propositional Attitudes" in
L. Linsky, ed:
Reference and Modality,
Oxford University Press, London, 1971, pp. 101-111

Gettier: "Is Justified True Belief Knowledge?",
Analysis
23, 1963, pp. 121-123

McCarthy, J.  and P. Hayes:  "Some Philosophical Problems from the
Standpoint of Artificial Intelligence",
in B.Meltzer and D.Michie, eds:
Machine Intelligence 4
Edinburgh University Press, 1969, pp. 463-502

Halpern and Moses:  "A Guide to the Modal Logics of Knowledge and Belief"
IJCAI
1985, pp. 480-490

Paradoxes

Introduction [10 pages.  This will
include a fairly complete summary of the work that's
been done on the Liar Paradox, since it's impossible to
fully understand the Knower Paradox papers without being aware
of what's been done on the Liar Paradox]

Kaplan, D.  and R. Montague:  "A Paradox Regained",
Notre Dame Journal of Formal Logic
1, 1960, pp. 79-90

Montague, R.:  "Syntactical Treatments of Modality with Corollaries on
Reflexion Principles and Finite Axiomatizability",
Acta Philosophica Fennica
16, 1963, pp. 153-167

Asher, N.  and H. Kamp: "The Knower's Paradox and Representational
Theories of Attitudes"
in J. Halpern, ed.:
Theoretical Aspects of Reasoning About Knowledge: Proceedings of the
1986 Conference,
Morgan Kaufmann, 1986, pp. 131-147

Morgenstern, L.:
Ch. 3,
Foundations of a Logic of Knowledge, Action, and Communication,
New York University Ph.D. Thesis, 1988 (abridged)

Kremer: Selection from
Logic and Truth,
Ph.D. Thesis, University of Pittsburgh, 1986

Perlis, D.:  "Self-Reference, Knowledge, Belief, and Modality"
AAAI
1986,
pp. 416-420 or
AIJ
vol 34, no. 2, 1988, pp. 179-212

Gaifman, H.:  Operational Pointer Semantics: Solutions to Self-Referential
Puzzles I"
in M. Vardi, ed.:
Proceedings of the Second Conference on Theoretical Aspects of Reasoning
About Knowledge,
Morgan Kaufmann, 1988, pp. 43-60

de Riviere, J.  and H. Levesque:
"The Consistency of Syntactical Treatments of Knowledge"
in J. Halpern, ed.:
Theoretical Aspects of Reasoning About Knowledge: Proceedings of the
1986 Conference,
Morgan Kaufmann, 1986, pp. 115-130

Thomason, R.: "A Note on Syntactical Treatments of Modality"
Synthese
44, 1980, pp. 391-395

Knowledge and Action
Introduction [5 pages]

Moore, R.:  "Formal Theories of Knowledge and Action" in
J. Hobbs and R. Moore, eds:
Formal Theories of the Commonsense World,
Ablex, 1985

Konolige, K.: "A First Order Formalization of Knowledge and Action for
a Multi-agent Planning System" in J.E. Hays and D. Michie, eds.
Machine Intelligence
10, 1982, also SRI TR 232, 1980

Haas, A.: "A Syntactic Theory of Belief and Action,"
Artificial Intelligence,
vol. 28, no. 3, 1986, pp. 245-292

Appelt, D.:
Planning Natural Language Utterances to Satisfy Multiple Goals,
SRI Technical Note 259, 1982 (selected chapter)

Morgenstern, L.: "Knowledge Preconditions for Actions and Plans"
IJCAI
1987, pp. 867-874

Rosenschein, S.: "Formal Theories of Knowledge in AI and Robotics"
CSLI Technical Report, 1987

Davis, E.:  "Inferring Ignorance from the Locality of Visual Perception"
AAAI
1988, pp. 786-790, or NYU TR 328, 1987

Cohen, P. and H. Levesque: "Persistence, Intention, and Commitment"
SRI TR 415, 1987.  Also in P. Cohen and M. Pollack, eds:
Proceedings, Symposium on Intentions and Plans in Communication and
Discourse,
1987.
or: "Rational Interaction as the Basis for Communication," same volume.

Moses, Y., D. Dolev, and J. Halpern: "Cheating Husbands and Other
Stories: A Case Study of Knowledge, Action, and Communication"
Distributed Computing,
Vol. 1, 1986, pp. 167-176

Halpern, J. and R. Fagin: "Modelling Knowledge and Action in Distributed
Systems," IBM TR RJ 6303 (61972), 6/17/88

Consequential Closure
Introduction [5 pages]

Vardi, M.:  "Epistemic Logic and Logical Omniscience" in
J Halpern, ed:
Theoretical Aspects of Reasoning About Knowledge: Proceedings of the 1986
Conference
Morgan Kaufmann, 1986, pp. 241-250

Eberle, R.:  "A Logic of Believing, Knowing, and Inferring"
Synthese,
Vol. 26, 1974, pp. 356-382

Konolige, K.: "Belief and Incompleteness" in
J. Hobbs and R. Moore, eds.:
Formal Theories of the Commonsense World,
Ablex, 1985. Abridged version.

Haas, A.:  "A Syntactic Theory of Belief and Action"
Artificial Intelligence,
Vol. 28, no. 3, 1986, pp. 245-292

Levesque, H.:  "A Logic of Implicit and Explicit Belief"
AAAI
1984, pp. 198-202

Fagin, R. and J. Halpern:  "Belief, Awareness, and Limited Reasoning"
IJCAI
1985, pp. 480-490. Longer version in
Artificial Intelligence,
Vol. 34, 1988, pp. 39-76

Konolige, K.:  "What Awareness Isn't: A Sentential View of Implicit and
Explicit Belief" in
J. Halpern, ed.:
Theoretical Aspects of Reasoning About Knowledge: Proceedings of the 1986
Conference,
Morgan Kaufmann, 1986, pp. 241-250

Drapkin, J.  and D. Perlis:  "Step-Logics:  An Alternative Approach to Limited
Reasoning,"
Proceedings of the European Conference on Artificial Intelligence,
1986

Epistemic Logic and Non-monotonic Reasoning

Introduction [7 - 10 pages, including a very brief sketch of the three
major non-monotonic formalisms]

Moore, R.: "Semantical Considerations on Nonmonotonic Logic,"
Artificial Intelligence,
Vol. 25, 1985, pp. 75-94

Konolige, K.: "On the Relationship between Default Theories and
Autoepistemic Logic,"
IJCAI
1987

Shoham, Y.: "Chronological Ignorance: Time, Nonmonotonicity,
and Necessity,"
AAAI
1986

Halpern, J. and Y. Moses: "Towards a Theory of Knowledge and Ignorance:
Preliminary Report," Technical Report RJ 4448 (48136), IBM San Jose
Research Lab, 1984.  Also in Proceedings, Nonmonotonic Reasoning Workshop,
New Paltz, 1984

Morgenstern, L: "Knowledge and the Frame Problem," in Kenneth Ford and
Patrick Hayes, eds:
Advances in Human and Machine Cognition, Vol. 1: The Frame Problem in
AI,
JAI Press, Greenwich, 1990
\vfill\end